﻿
//template <class T1, class T2>
//struct pair
//{
//	typedef T1 first_type;
//	typedef T2 second_type;
//	T1 first;
//	T2 second;
//	pair() : first(T1()), second(T2())
//	{}
//	pair(const T1& a, const T2& b) : first(a), second(b)
//	{}
//};
//#include<map>
//#include<set>
//#include<string>
//#include<iostream>
//using namespace std;


//set<string> s1; //构造一个string类型的空set
//
//string str = "hello world";
//set<char> s2(str.begin(),str.end()); 
////用[str.begin(), str.end())区间中的元素构造set
//
//set<string> s3(s1); //拷贝构造


//void TestSet()
//{
//    // 用数组array中的元素构造set
//    int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
//
//    set<int> s(array, array + sizeof(array) / sizeof(array[0]));
//
//    cout << s.size() << endl; //10
//
//    // 正向打印set中的元素，从打印结果中可以看出：set可去重
//    for (auto& e : s)
//        cout << e << " ";  //0 1 2 3 4 5 6 7 8 9
//    cout << endl;
//
//    //删除元素8
//    s.erase(8);
//    //查找元素9，删除
//    set<int>::iterator ptr = s.find(9); 
//    if (ptr != s.end())
//    {
//        s.erase(ptr);
//    }
//
//    // 使用迭代器逆向打印set中的元素
//    for (auto it = s.rbegin(); it != s.rend(); ++it)
//        cout << *it << " ";   //7 6 5 4 3 2 1 0
//    cout << endl;
//
//    // set中值为3的元素出现了几次
//    cout << s.count(3) << endl; // 1
//}



//void TestSet()
//{
//    int array[] = { 2, 1,4,4,3,9,6,8,8,8 };
//
//    // 注意：multiset在底层实际存储的是<int, int>的键值对
//    multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
//    for (auto& e : s)
//        cout << e << " "; //1 2 3 4 4 6 8 8 8 9
//    cout << endl;
//
//    // set中没有重复元素，元素存在count返回1，不在返回0
//    // multiset可以返回重复元素的个数
//    cout << s.count(8) << endl; // 3
//}



//map <string,int> m1; //构造一个key为string类型，value为int类型的空map
//
//map<string, int> m2(m1.begin(), m1.end());
////用[m1.begin(), m2.end())区间中的元素构造map
//
//map<string,int> m3(m2); //拷贝构造


//#include <string>
//#include <map>
//void TestMap()
//{
//    map<string, string> m;
//
//    // 向map中插入元素的方式：
//    // 1.将键值对<"red","红色">插入map中，用pair直接来构造键值对
//    m.insert(pair<string, string>("red", "红色"));
//
//    // 2.将键值对<yellow", "黄色">插入map中，用make_pair函数来构造键值对
//    m.insert(make_pair("yellow", "黄色"));
//
//
//    // 3.借用operator[]向map中插入元素
///*
//    operator[]的原理是：
//     用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
//     如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
//     如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
//     operator[]函数最后将insert返回值键值对中的value返回
//*/
//    // 将<"green", "">插入map中，插入成功，返回value的引用，将“绿色”赋值给该引用结果
//    m["green"] = "绿色";
//
//    // key不存在时抛异常
//    //m.at("pink") = "粉色";
//    cout << m.size() << endl;  // 3
//
//
//    // 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列
//    for (auto& e : m)
//        cout << e.first << "-->" << e.second << endl; //green-->绿色
//    cout << endl;                                     //red-- > 红色
//                                                      //yellow-- > 黄色
//    
//
//    // map中的键值对key一定是唯一的，如果key存在将插入失败
//    //auto类型<iterator,bool>
//    auto ret = m.insert(make_pair("red", "红色"));
//    if (ret.second)
//        cout << "<red, 红色>不在map中, 已经插入" << endl;
//    else
//        cout << "键值为red的元素已经存在：" << ret.first->first << "-->"
//        << ret.first->second << " 插入失败" << endl;
//
//
//    // 删除key为"red"的元素
//    m.erase("green");
//    if (1 == m.count("green"))
//        cout << "green存在" << endl;
//    else
//        cout << "green不存在" << endl;
//}
//
//
//
//int main()
//{
//    TestMap();
//    return 0;
//}




//template<class T>
//struct AVLTreeNode
//{
//    AVLTreeNode(const T& data)
//        : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
//        , _data(data), _bf(0)
//    {}
//    AVLTreeNode<T>* _pLeft;   // 该节点的左孩子
//    AVLTreeNode<T>* _pRight;  // 该节点的右孩子
//    AVLTreeNode<T>* _pParent; // 该节点的双亲
//    T _data;
//    int _bf;                  // 该节点的平衡因子
//};



//1. 先按照二叉搜索树的规则将节点插入到AVL树中
//
//2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树的平衡性, cur插入后，parent的平衡因子一定需要调整，在插入之前，parent 的平衡因子分为三种情况： - 1，0, 1, 分以下两种情况：
//
//1. 如果cur插入到parent的左侧，只需给parent的平衡因子 - 1即可
//
//2. 如果cur插入到parent的右侧，只需给parent的平衡因子 + 1即可, 此时：parent的平衡因子可能有三种情况：0，正负1，正负2，1。如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功
//
//2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此时以parent为根的树的高度增加，需要继续向上更新
//
//3. 如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理 



#include<iostream>
#include"work_RBTree.h"
using namespace std;

int main()
{
	return 0;
}
